Bölüm Özeti

Graf veri modeli, düğümler ve ilişkilerin düğümler arası bağlantılarla gösterildiği bir veri modelidir. Bilgisayar, kimya, makina gibi birçok disiplin için gerekli modellemelerde sıkça kullanılmaktadır. Graflar üzerine olan tanımların ve teoremleri bilinmesi ve onun üzerine geliştirilmiş olan algoritmaların anlaşılmış olması, çözülmez gibi görünen birçok probleme algoritmik çözüm sunar.

Grafların bellek üzerinde tutulması için temelde matris, iki-dizi, bağlantılı liste ve dizili-bağlantılı liste olarak adlandırılan dört temel yöntem kullanılır. Eğer graf seyrek özellikte ise iki dizi ve dizili-bağlantılı liste, graf yoğun ise matris üzerinde tutulması daha iyi sonuç vermektedir denilebilir.

Graf üzerindeki komşu olmayan düğümlere farklı renk atanması işlemine graf renklendirme denilir; uygulamada, haritada bölgelerin boyanmasına ve en uygun atama yapılması gibi birçok problemin çözümüne graf renklendirme algoritmik yaklaşım sunmaktadır.

Graf üzerinde dolaşma için, kısaca, birisi DFS diğeri BFS olarak adlandırılan iki temel yaklaşım vardır. DFS, önce bir kenar üzerinden gidilebilecek en derin yere kadar gider; BFS'de ise önce bir düğümden gidilebilecek diğer tüm düğümlere gidilir.